/**和至少为 K 的最短子数组
 * 给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，
 * 并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
子数组 是数组中 连续 的一部分。
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var shortestSubarray = function (nums, k) {
  const n = nums.length;
  // nums = [2,-1,2], k = 3 输出3
  // nums = [1,2], k = 4 输出-1
  // 前缀和的数组 【0,2,1,3】
  const prefixSum = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) {
    prefixSum[i + 1] = prefixSum[i] + nums[i];
  }
  let minLength = Infinity;
  // 单调队列，存储前缀和数组的索引
  const queue = [];
  for (let i = 0; i <= n; i++) {
    // 当队列不为空且当前前缀和减去队首元素对应的前缀和大于等于 k 时，更新最短长度
    while (queue.length > 0 && prefixSum[i] - prefixSum[queue[0]] >= k) {
      minLength = Math.min(minLength, i - queue.shift());
    }
    // 维护队列的单调性，将比当前前缀和大的元素从队尾移除
    while (queue.length > 0 && prefixSum[i] <= prefixSum[queue[queue.length - 1]]) {
      queue.pop();
    }
    // 将当前索引加入队列
    queue.push(i);
  }
  return minLength === Infinity ? -1 : minLength;
};

/**验证有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  // ([]) ()[]{}
  // 有几个左括号就有几个右括号 有来有回；第一个右括号一定对应最后一个左括号
  // 创建一个空栈用于存储左括号
  let stack = [];
  let map = {
    ')': '(',
    '}': '{',
    ']': '['
  };
  // 遍历字符串中的每个字符
  for (let i = 0; i < s.length; i++) {
    let char = s[i];
    //   ([{
    if (char === '(' || char === '{' || char === '[') {
      // 如果是左括号，直接压入栈中
      stack.push(char);
    } else {
      // 如果是右括号，检查栈顶元素是否匹配
      if (stack.length === 0) {
        return false;
      }
      const stackpop = stack.pop();
      if (stackpop !== map[char]) {
        return false;
      }
    }
  }
  // 遍历完字符串后，如果栈为空，说明所有括号都正确闭合
  return stack.length === 0;
};

/**旋转排序数组中的最小值
 *给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，
 进行了多次旋转。请你找出并返回数组中的 最小元素
 * 例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
 * @param {number[]} nums
 * @return {number}
 */
function findMin(nums) {
  let left = 0,
    right = nums.length - 1;
  // [4, 5, 6, 7, 0, 1, 2] 二分查找
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    // 如果中间元素大于最右边元素，说明最小值在右半部分
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      // 否则最小值在左半部分（包括中间元素）
      right = mid;
    }
  }
  // 最终 left 和 right 会指向最小值的位置
  return nums[left];
}

/**滑动窗口最大值/最小值
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
 * 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
   返回 滑动窗口中的最大值 。
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function slidingWindowMaxMin(nums, k) {
  const n = nums.length;
  if (n === 0 || k === 0) {
    return [[], []];
  }
  const maxValues = [];
  const minValues = [];
  const maxQueue = [];
  const minQueue = [];
  // [1, 3, -1, -3, 5, 3, 6, 7]   3
  // 输出: [ [ 3, 3, 5, 5, 6, 7 ], [ -1, -3, -3, -3, 3, 3 ] ]
  for (let i = 0; i < n; i++) {
    // 维护最大值队列的单调性
    while (maxQueue.length > 0 && nums[maxQueue[maxQueue.length - 1]] < nums[i]) {
      maxQueue.pop();
    }
    maxQueue.push(i);
    // 维护最小值队列的单调性
    while (minQueue.length > 0 && nums[minQueue[minQueue.length - 1]] > nums[i]) {
      minQueue.pop();
    }
    minQueue.push(i);
    // 检查窗口大小
    if (i >= k - 1) {
      // 检查队列头部的元素是否已经超出了当前窗口的范围
      while (maxQueue.length > 0 && maxQueue[0] <= i - k) {
        maxQueue.shift();
      }
      while (minQueue.length > 0 && minQueue[0] <= i - k) {
        minQueue.shift();
      }
      // 队列头部的元素即为当前窗口的最大值和最小值
      maxValues.push(nums[maxQueue[0]]);
      minValues.push(nums[minQueue[0]]);
    }
  }
  return [maxValues, minValues];
}
console.log(slidingWindowMaxMin([1, 3, -1, -3, 5, 3, 6, 7], 3));

/**
 * 数组中最长连续序列的长度。
 * @param {number[]} nums - 输入的整数数组。
 * @return {number} - 最长连续序列的长度。
 */
function longestConsecutive(nums) {
  // 将数组元素存入 Set 集合，方便快速查找
  const numSet = new Set(nums);
  let maxLength = 0;
  for (const num of numSet) {
    // 检查当前元素是否为连续序列的起始元素
    if (!numSet.has(num - 1)) {
      let currentNum = num;
      let currentLength = 1;
      // 从当前元素开始，不断递增，检查是否存在于 Set 中
      while (numSet.has(currentNum + 1)) {
        currentNum++;
        currentLength++;
      }
      // 更新最长连续序列的长度
      maxLength = Math.max(maxLength, currentLength);
    }
  }
  return maxLength;
}
/**无重复字符的最长子串-滑动窗口
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  // 输入: s = "abcbcbb"
  // 输出: 3
  // 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
  if (typeof s !== 'string') {
    throw new Error('Input must be a string');
  }
  // 处理边界条件
  if (s.length <= 1) {
    return s.length;
  }
  const seen = new Set();
  let maxLength = 0;
  let left = 0;
  for (let right = 0; right < s.length; right++) {
    // 当遇到重复字符时，移动左指针(abcabcbb)
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    maxLength = Math.max(maxLength, seen.size);
  }
  return maxLength;
};
/**三数之和-双指针
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
 * 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
 * 答案中不可以包含重复的三元组。
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  // 1.先排序
  nums = nums.sort((a, b) => a - b);
  let res = [];
  // [-4,-1,-1,0,1,2]
  // 使用 nums.length - 2 是为了确保在遍历数组时，留出足够的空间给双指针（left 和 right）进行操作
  for (let i = 0; i < nums.length - 2; i++) {
    // 跳过重复的 i 值
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      const num = nums[i] + nums[left] + nums[right];
      if (num === 0) {
        res.push([nums[i], nums[left], nums[right]]);
        // 考虑去重，相邻两数不要相同，相同时，指针继续移动
        while (nums[left] === nums[left + 1] && left < right) {
          left++;
        }
        while (nums[right] === nums[right - 1] && left < right) {
          right--;
        }
        // 找到答案时，双指针同时收缩
        left++;
        right--;
      } else if (num > 0) {
        right--;
      } else if (num < 0) {
        left++;
      }
    }
  }
  return res;
};

/**最接近的三数之和-双指针
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 * 返回这三个数的和。
 * 假定每组输入只存在恰好一个解。
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
  // 输入验证
  // if (!Array.isArray(nums) || !nums.every(Number.isFinite)) {
  //   throw new Error('Input must be an array of numbers');
  // }
  // 处理边界条件
  if (nums.length < 3) {
    return null; // 或者返回 undefined
  }
  // 1.先排序
  nums = nums.sort((a, b) => a - b);
  let res = Infinity; // 初始化一个最大值，先让差值最大
  // [-4,-1,-1,0,1,2] 0
  for (let i = 0; i < nums.length - 2; i++) {
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      // 只要sum与target的绝对值比上次的res的绝对值小，就更新res
      if (Math.abs(sum - target) < Math.abs(res - target)) {
        res = sum;
      }
      if (sum < target) {
        left++;
      } else if (sum > target) {
        right--;
      } else {
        return sum;
      }
    }
  }
  return res;
};

/**删除有序数组中的重复项-双指针
 * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次,
 * 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
 *    更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。
 *    nums 的其余元素与 nums 的大小不重要。返回 k 。
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  // 输入：nums = [0,0,1,1,1,2,2,3,3,4]
  // 输出：5, nums = [0,1,2,3,4]
  if (nums.length === 0) return 0;
  let slow = 0;
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast];
    }
  }
  return slow + 1;
};
/**移动零-双指针
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 * @param {number[]} nums
 * @return nums
 */
var moveZeroes = function (nums) {
  // 输入: nums = [0,1,0,3,12] 不是0就移动
  // 输出: [1,3,12,0,0]
  let left = 0;
  // 遍历数组
  for (let right = 0; right < nums.length; right++) {
    if (nums[right] !== 0) {
      // 交换非零元素到 left 指针位置
      [nums[left], nums[right]] = [nums[right], nums[left]];
      // left 指针右移
      left++;
    }
  }
  return nums;
};
/**两数之和-Map集合查找
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target  的那 两个 整数，
 * 并返回它们的数组下标。]
 * @param {number[]} nums
 * @return {number[][]}
 */
var twoSum = function (nums, target) {
  // nums = [2,7,11,15], target = 9    [0,1]
  const numMap = new Map(); // [[2,0],[7,1],[11,2],[15,3]]
  for (let i = 0; i < nums.length; i++) {
    const num2 = target - nums[i];
    if (numMap.has(num2)) {
      return [i, numMap.get(num2)];
    }
    numMap.set(nums[i], i);
  }
  return [];
  // 暴力解法
  const n = nums.length;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; i++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
};
const indexarr = twoSum([2, 7, 11, 15], 13);
/*盛最多水的容器-双指针
      给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
     * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     * 返回容器可以储存的最大水量。
     * 注意：你不能倾斜容器。
     * 示例 1：
     * 输入：height = [1,8,6,2,5,4,8,3,7]
     * 输出：49
     * 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
     * @param {number[]} height
     * @return {number}
     */
var maxArea = function (height) {
  let maxArea = 0;
  let left = 0;
  let right = height.length - 1;
  while (left < right) {
    const area = Math.min(height[left], height[right]) * (right - left);
    maxArea = Math.max(maxArea, area);
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  return maxArea;
};

// 344. 反转字符串
var reverseString = function (s) {
  const n = s.length;
  for (let i = 0; i < n; i++) {
    const endIndex = n - 1 - i;
    if (i < endIndex) {
      [s[i], s[endIndex]] = [s[endIndex], s[i]];
    }
  }
  return s;
};
reverseString(['h', 'e', 'l', 'l', 'o']);
